package org.laizili.solution.leetcode;

import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation/">762. 二进制表示中质数个计算置位</a>
 * <p>
 * tags: 位运算; 素数
 * </p>
 */
public class Problem762 {
    /*
     * 素数筛
     */
    private static class Solution {
        // int型计算机内部用 32 bit表示，因此最多有 32 bit置1
        private static final int LEN = 32 + 1;
        private static final boolean[] isPrime = new boolean[LEN];

        static {
            Arrays.fill(isPrime, 2, LEN, true);
            for (int i = 2; i < LEN; i++) {
                if (isPrime[i]) {
                    for (int k = 2; i * k < LEN; k++) {
                        isPrime[k * i] = false;
                    }
                }
            }
        }

        public int countPrimeSetBits(int left, int right) {
            int cnt = 0;
            for (int i = left; i <= right; i++) {
                if (isPrime[Integer.bitCount(i)]) {
                    cnt++;
                }
            }
            return cnt;
        }
    }

    //方法二 位运算
    private static class Solution2 {
        // 结合题目信息，题目输入的数 num 的二进制表示中最多只有 20 个 1 (1<=num<=1000000)
        // 小于等于20的质数有：2 3 5 7 11 13 17 19
        // 构造如下 mask
        private static final int mask = 0b10100010100010101100;

        public int countPrimeSetBits(int left, int right) {
            int cnt = 0;
            for (int i = left; i <= right; i++) {
                //mask & (1 << the number of bit) != 0， 则表示该数的二进制表示汇总含有质数个1
                if ((mask & (1 << Integer.bitCount(i))) != 0) {
                    cnt++;
                }
            }
            return cnt;
        }
    }
}
